package com.jwetherell.my.problems.patternsearching;

/**
 * http://www.geeksforgeeks.org/pattern-searching-set-4-a-naive-string-matching-algo-question/
 * 
 * Consider a situation where all characters of pattern are different. Can we
 * modify the original Naive String Matching algorithm so that it works better
 * for these types of patterns. If we can, then what are the changes to original
 * algorithm?
 * 
 * @author yatendra
 * 
 */
public class NaivePatternSearch_ModifiedForASpecialPattern {

	public static void main(String[] args) {
		// String textStr = "AABAACAADAABAAABAA";
		// String patternStr = "AABA";

		// String textStr = "AAAAAAAAAAAAAAAAAA";
		// String patternStr = "AAAAA";

//		String textStr = "AAAAAAAAAAAAAAAAAB";
//		String patternStr = "AAAAB";

//		String textStr = "abcabcdefxyzutivabcdef";
//		String patternStr = "abcdef";
		
		String textStr = "ABCEABCDABCEABCD";
		String patternStr = "ABCD";
		
		char[] text = textStr.toCharArray();
		char[] pattern = patternStr.toCharArray();

		NaivePatternSearch_ModifiedForASpecialPattern patternSearch = new NaivePatternSearch_ModifiedForASpecialPattern();
		patternSearch.printPatternIndices(text, pattern);
	}

	private void printPatternIndices(char[] text, char[] pattern) {

		for (int i = 0; i < text.length - pattern.length + 1; i++) {

			int j;
			for (j = 0; j < pattern.length; j++) {
				if (text[i + j] != pattern[j]) {
					break;
				}
			}

			if (j == pattern.length)
				System.out.println("Pattern found at index " + i);

			/**
			 * below two lines are the extra lines added to our original NaivePatternSearch algorithm
			 */
			if (j!=0)
				i += j-1;
			
		}
	}
}